package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class fourteen2 {
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> list=new ArrayList<>();
        HashMap<Character,Integer> hashMap=new HashMap<>();
        int n=p.length();
        int m=s.length();
        for(int i=0;i<n;i++){
            char in=p.charAt(i);
            hashMap.put(in, hashMap.getOrDefault(in,0)+1);
        }
        int left=0;
        int right=0;
        HashMap<Character,Integer> hashMap1=new HashMap<>();
       for( left=0, right=0;right<m;right++){
           char in=s.charAt(right);
           hashMap1.put(in, hashMap1.getOrDefault(in,0)+1);
          if(right==left+n-1){
              if(hashMap.equals(hashMap1)){
                  list.add(left);
              }
              char out=s.charAt(left);
              hashMap1.put(out,hashMap1.get(out)-1);
              if(hashMap1.get(out)==0){
                  hashMap1.remove(out);
              }
              left++;
          }
       }
       return list;
    }

    public static void main(String[] args) {
//        s = "cbaebabacd", p = "abc"
        String s="cbaebabacd";
        String p="abc";
        List<Integer> anagrams = findAnagrams(s, p);
        System.out.println(anagrams);
    }
}
